Search results for "Empty string"
showing 2 items of 2 documents
On the use of relational expressions in the design of efficient algorithms
2005
Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (−1), and union (U). The efficient computation of the relation denoted by a relational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
N-string vertices in string field theory.
1993
We give the general form of the vertex corresponding to the interaction of an arbitrary number of strings. The technique employed relies on the ``comma" representation of String Field Theory where string fields and interactions are represented as matrices and operations between them such as multiplication and trace. The general formulation presented here shows that the interaction vertex of N strings, for any arbitrary N, is given as a function of particular combinations of matrices corresponding to the change of representation between the full string and the half string degrees of freedom.